
import java.io.File;
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.Stream;

class Interval{
    int start;
    int end;
    Interval(){start=0;end=0;}
    Interval(int s,int e){start=s;end=e;}


    @Override
    public String toString() {
        final StringBuffer sb = new StringBuffer("Interval{");
        sb.append("start=").append(start);
        sb.append(", end=").append(end);
        sb.append('}');
        return sb.toString();
    }
}
public class ArrayOperationDemo{
    private static ArrayList<ArrayList<Integer>> zeroMatrix;

    public static void main(String[] args) {
        int[][] x = new int[][]{{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}};
        int y[] = new int[]{8504,3320,23905,2662,22664,9423,28869,11825,28558,7148,3321,23906,3321,3322,3323,3324,23907};
//        ArrayList<ArrayList<Integer>> value = subsets(y);
//        for (int i = 0; i < value.size(); i++) {
//            for (int j = 0; j < value.get(i).size(); j++) {
//                System.out.print(value.get(i).get(j)+" ");
//            }
//            System.out.println();
//        }
//        ArrayList<Integer> integers = spiralOrder(x);
//        ArrayList<ArrayList<Integer>> matrix = new ArrayList<>();
//
//        ArrayList<Integer> res = new ArrayList<>();
//        res.add(1);
//        res.add(2);
//        res.add(3);
//        matrix.add(res);
//        ArrayList<Integer> res1 = new ArrayList<>();
//        res1.add(4);
//        res1.add(5);
//        res1.add(6);
//        matrix.add(res1);
//        setZeroMatrix(matrix);
//        System.out.println("integers.toString() = " + integers.toString());
//        String [][]str = new String[][]{{"123","160","180"},{"aaa120","180","160"},{"abc123","140","180"}};
//        String[][] array = getArray2(str);
//        for (int i = 0; i < array.length; i++) {
//            for (int j = 0; j < array[i].length; j++) {
//                System.out.print("array[i][j] = " + array[i][j]);
//            }
//            System.out.println();
//        }
//        int value = MLS(y);
//        System.out.println("value = " + value);
//        ArrayList<Interval> intervals = new ArrayList<>();
//        intervals.add(new Interval(10,30));
//        intervals.add(new Interval(20,60));
//        intervals.add(new Interval(80,150));
//        intervals.add(new Interval(150,180));
//        intervals.add(new Interval(1,4));
//        intervals.add(new Interval(0,2));
//        ArrayList<Interval> result = merge(intervals);
//        result.stream().forEach(s->{
//            System.out.println("s.toString() = " + s.toString());
//        });
        int A[] = new int[]{4,5,6,0,0,0};
        int B[] = new int[]{1,2,3};
//        mergeArray(A,A.length,B,3);
        int num[] =new int[]{100,10,20,70,60,10,50};
        int target = 80;
        ArrayList<ArrayList<Integer>> result =  combinationSum2(num,target);
        result.forEach(System.out::println);
    }

    private static ArrayList<ArrayList<Integer>> combinationSum2(int[] num, int target) {
        HashMap<Integer,Integer> test  = new HashMap<>();
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        ArrayList<Integer> arr = new ArrayList<>();
        if(num ==null ||num.length==0||target<0) return result;
        Arrays.sort(num);
        dfs(num,target,result,arr,0);
        return result;
    }

    private static void dfs(int[] num, int target, ArrayList<ArrayList<Integer>> result, ArrayList<Integer> arr, int start) {

        arr.stream().forEach(System.out::print);System.out.println();
        if(target==0){
            result.add(new ArrayList<Integer>(arr));
            return;
        }
        if(start >= num.length) return;
        for (int i = start; i < num.length; i++) {
            if( i> start && num[i]==num[i-1]) continue;
            if(num[i]<=target){
                arr.add(num[i]);
                dfs(num,target-num[i],result,arr,i+1);
                arr.remove(arr.size()-1);
            }

        }
        return;
    }

    private static void mergeArray(int[] a, int m, int[] b, int n) {
//        for (int i = 0; i < n; i++) {
//            a[m+i] = b[i];
//        }
        for (int i = 0; i < n; i++) {
            a[m-n+i]=b[i];
        }
        Arrays.sort(a);
        Arrays.stream(a).forEach(System.out::print);
    }

    private static ArrayList<Interval> merge(ArrayList<Interval> intervals) {
//        ArrayList<Interval>result=new ArrayList<>();
//        if(intervals.size()==1)result.add(intervals.get(0));
//        int i=0;
//        for(int j=i+1;i<intervals.size()&&j<intervals.size();){
//            Interval val1=intervals.get(i);
//            int start=0,end=0;
//            Interval val2=intervals.get(j);
//            intervals.stream().forEach(System.out::print);
//            System.out.println(i+" "+j+" val1="+val1+" val2="+val2);
//            if(val1.end>=val2.start&&val1.end>=val2.end&&val1.start>=val2.start&&val1.start>=val2.end){
//                System.out.println(" if " );
//                intervals.set(i,val2);intervals.set(j,val1);i++;j++;
//            }else if(val1.start>=val2.start||val1.start>=val2.end){
//                start=Math.min(val2.start,val2.end);
//                end=Math.max(val1.end,val2.end);
//                intervals.set(i,new Interval(start,end));
//                intervals.remove(j);
//            }else if(val1.end>=val2.start||val1.end>=val2.end){
//                start=val1.start;
//                end=Math.max(val1.end,val2.end);
//                intervals.set(i,new Interval(start,end));
//                intervals.remove(j);
//            }else{
//                intervals.set(i,val1);intervals.set(j,val2);i++;j++;
//            }
//
//        }
//        System.out.println("i = " + i);
//        intervals.stream().forEach(System.out::println);
//        result.addAll(intervals.stream().limit(i+1).collect(Collectors.toList()));
//        return result;
        Collections.sort(intervals, new Comparator<Interval>() {
            @Override
            public int compare(Interval o1, Interval o2) {
                if(o1.start!=o2.start) return o1.start-o2.start;
                else return o1.end-o2.end;
            }
        });
        ArrayList<Interval>result=new ArrayList<>();
        if(intervals.size()>=1)result.add(intervals.get(0));
        int i = 0;
        for (int j = 1; j < intervals.size(); j++) {
            Interval str1 = intervals.get(j);
            Interval original = result.get(i);
            if(str1.start > original.end){
                result.add(str1);
                i++;
            }else{
                result.remove(i); // 重叠了
                Interval s = new Interval(original.start,Math.max(original.end,str1.end));
                result.add(s);
            }
        }
        return result;
    }

    private static String[][] getArray2(String[][] str) {
//        Arrays.sort(str, new Comparator<String[]>() {
//            @Override
//            public int compare(String[] o1, String[] o2) {
          Arrays.sort(str,(String []o1,String []o2)->{
                int swap = 0;
                for (int i = 0; i < o1.length&&i<o2.length; i++) {
                    String str1 = o1[i];
                    String str2 = o2[i];
                    int str1Length = 0,str2Length=0;
                    while (str1Length<str1.length() && !(str1.charAt(str1Length)>='0' && str1.charAt(str1Length)<='9')){
                        str1Length++;
                    }
                    while (str2Length<str2.length() && !(str2.charAt(str2Length)>='0' && str2.charAt(str2Length)<='9')){
                        str2Length++;
                    }
                    for (int j = str1Length,k=str2Length; j < str1.length() && k<str2.length(); j++,k++) {
                        if(str1.charAt(j)>str2.charAt(k)) return 1;
                        else if(str1.charAt(j)<str2.charAt(k)) return -1;
                    }
                }
                return swap;
//            }
        });
        return str;
    }

    private static int MLS(int[] arr) {

        Arrays.sort(arr);
        int length = 0;
        int record = 1;
        for (int i = 0; i < arr.length-1; i++) {
            if(arr[i+1]==arr[i]+1){
                record++;
            }else if (arr[i+1]==arr[i]) continue;
            else record=1;
            length = Math.max(length,record);
        }
        return length;
    }

    private static ArrayList<ArrayList<Integer>> subsets(int[] s) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        Arrays.sort(s);
        ArrayList<Integer> sub = new ArrayList<>();
        result.add(sub);
        for (int i = 0; i < s.length; i++) {
            ArrayList<ArrayList<Integer>> newres1 = new ArrayList<>();
            for (int j = 0; j < result.size(); j++) {
                ArrayList<Integer> newres = new ArrayList<>();
                newres.addAll(result.get(j));
                newres.add(s[i]);
                newres1.add(newres);
            }
            result.addAll(newres1);
        }
        return result;
    }

    public static String[][] getArray(String [][]str){
        for (int i = 0; i < str.length; i++) {
            int swap = 0;
            String str1;
            int swapIndex = i;
            for (int j = i+1,k = 0; j < str[i].length; j++) {
                str1 = str[i][k];
                String str2 = str[j][k];
                // 去掉字符
                swap = getSort(str[swapIndex][k],str2);
                System.out.print("swap = " + swap);
                System.out.print("str2 = " + str2);
                System.out.print("str1 = " + str1);
                System.out.print("swapIndex = " + swapIndex);
                // 代表需要换
                if(swap>0) {
                    swapIndex = j;
                } else if(swap==0) {k++;j--;}
                else break;
            }
            System.out.println();
            if(swapIndex!=i){
                // 说明前面的大，换
                String[] strings = str[i];
                str[i] = str[swapIndex];
                str[swapIndex] = strings;
            }else if(swap < 0 ){

            }
        }
        return str;
    }

    private static int getSort(String str1, String str2) {
        int swap = 0;
        int str1Length = 0,str2Length=0;
        while (str1Length<str1.length() && !(str1.charAt(str1Length)>='0' && str1.charAt(str1Length)<='9')){
            str1Length++;
        }
        while (str2Length<str2.length() && !(str2.charAt(str2Length)>='0' && str2.charAt(str2Length)<='9')){
            str2Length++;
        }
        while (str1Length<str1.length() && str2Length <str2.length()) {
            if(str1.charAt(str1Length) > str2.charAt(str2Length)) {
                swap = 1;break;
            }else if(str1.charAt(str1Length) < str2.charAt(str2Length)){
                swap = -1;break;
            }else{
                str1Length++;
                str2Length++;
            }
        }
        return swap;
    }

    public static ArrayList<Integer> spiralOrder(int [][]matrix){
        ArrayList<Integer> result= new ArrayList<>();
        int lTop = 0,rTop = matrix.length-1;
        int lDown = 0,rDown = matrix[lDown].length-1;
        while (lTop <= lDown && rTop<=rDown){
            // 上面一层
            for (int i = lTop; i <= rDown; i++) {
                result.add(matrix[lTop][i]);
            }
            lTop++;
            if(lTop > rTop )break;
            // 右边一层
            for (int i = lTop; i <= rTop; i++) {
                result.add(matrix[i][rDown]);
            }
            rDown--;
            if(rDown < lDown) break;
            //最底一层
            for (int i = rDown; i >= lDown; i--) {
                result.add(matrix[rTop][i]);
            }
            rTop--;
            if(lTop > rTop) break;
            // 左边
            for (int i = rTop; i >= lTop; i--) {
                result.add(matrix[i][lDown]);
            }
            lDown++;
            if(rDown < lDown) break;
        }
        return result;
    }

    public static void setZeroMatrix(ArrayList<ArrayList<Integer>> zeroMatrix) {
        ArrayList<Integer> rows = new ArrayList<>();
        for (int i = 0; i < zeroMatrix.size(); i++) {
            for (int j = 0; j < zeroMatrix.get(i).size(); j++) {
                if(zeroMatrix.get(i).get(j)==0){
                    rows.add(j);
                }
            }
            if(rows.size()>0){
                // 该行置为0
                for (int j = 0; j < zeroMatrix.get(i).size(); j++) {
                    zeroMatrix.get(i).set(j,0);
                }
            }
        }

        for (int i = 0; i < zeroMatrix.size(); i++) {
            for (int j = 0; j < rows.size(); j++) {
                zeroMatrix.get(i).set(j,0);
            }
        }
    }
}

